#include <deque>
#include <iostream>
using namespace std;

const int kMaxN = 1e6 + 10;

int a[kMaxN];

void GetMin(int n, int k) {
  deque<int> deq;

  for (int i = 0; i < k - 1; i++) {
    for (; !deq.empty() && a[deq.back()] >= a[i]; deq.pop_back());
    deq.push_back(i);
  }
  for (int i = 0; i + k <= n; i++) {
    for (; !deq.empty() && a[deq.back()] >= a[i + k - 1]; deq.pop_back());
    deq.push_back(i + k - 1);
    cout << a[deq.front()] << " ";
    if (deq.front() <= i) {
      deq.pop_front();
    }
  }
  cout << "\n";
}

void GetMax(int n, int k) {
  deque<int> deq;

  for (int i = 0; i < k - 1; i++) {
    for (; !deq.empty() && a[deq.back()] <= a[i]; deq.pop_back());
    deq.push_back(i);
  }
  for (int i = 0; i + k <= n; i++) {
    for (; !deq.empty() && a[deq.back()] <= a[i + k - 1]; deq.pop_back());
    deq.push_back(i + k - 1);
    cout << a[deq.front()] << " ";
    if (deq.front() <= i) {
      deq.pop_front();
    }
  }
  cout << "\n";
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int n, k;

  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  GetMin(n, k);
  GetMax(n, k);
  return 0;
}